package com.hqq.exercise.tree;

/**
 * JudgeSubTree 判断子树
 * 题目描述:
 * 输入两颗二叉树A和B，判断B是不是A的子结构
 * Created by heqianqian on 2017/8/11.
 */
public class JudgeSubTree {

    public static boolean isSubTree(TreeNode supTree, TreeNode subTree) {
        boolean result = false;
        if (subTree != null && supTree != null) {
            if (subTree.val == supTree.val) {
                result = doesHaveSubTree(supTree, subTree);
                if (!result) {
                    result = isSubTree(supTree.left, subTree);
                }
                if (!result) {
                    result = isSubTree(supTree.right, subTree);
                }
            }
        }
        return result;
    }

    private static boolean doesHaveSubTree(TreeNode supTree, TreeNode subTree) {
        if (subTree == null) {
            return true;
        } else if (supTree == null) {
            return false;
        }
        return subTree.val == supTree.val && doesHaveSubTree(supTree.left, subTree.left) && doesHaveSubTree(supTree.right, supTree.right);
    }

    /**
     * 找到subTree的根节点在supTree中的位置
     */
    public static TreeNode findRootInParent(TreeNode supTree, TreeNode subTree) {
        if (supTree.val == subTree.val) {
            return subTree;
        }
        if (supTree.left != null) {
            findRootInParent(supTree.left, subTree);
        }
        if (supTree.right != null) {
            findRootInParent(supTree.right, subTree);
        }
        return null;
    }

}
